﻿#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

// 交换两个整数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 随机化分区函数，用于随机选择算法
// 将数组a[p..r]以随机选择的基准分为两部分，返回基准位置
int randomizedPartition(int a[], int p, int r) {
    // 随机选择一个元素作为基准
    int randIndex = p + rand() % (r - p + 1);
    swap(&a[randIndex], &a[r]);

    int pivot = a[r];  // 基准值
    int i = p - 1;     // i标记小于基准区域的边界

    // 遍历数组，将小于等于基准的元素放到左侧
    for (int j = p; j <= r - 1; j++) {
        if (a[j] <= pivot) {
            i++;
            swap(&a[i], &a[j]);
        }
    }

    // 将基准放到正确位置
    swap(&a[i + 1], &a[r]);
    return i + 1;  // 返回基准位置
}

// 随机选择算法（迭代实现）
// 查找数组a[p..r]中第k小的元素
int randomizedSelect(int a[], int p, int r, int k) {
    while (1) {
        if (p == r) {
            return a[p];
        }

        int pivotPos = randomizedPartition(a, p, r);
        int leftCount = pivotPos - p + 1;

        if (k <= leftCount) {
            r = pivotPos;
        }
        else {
            p = pivotPos + 1;
            k -= leftCount;
        }
    }
}

// 插入排序，用于小规模数组排序
void insertionSort(int a[], int p, int r) {
    for (int i = p + 1; i <= r; i++) {
        int key = a[i];
        int j = i - 1;

        // 将大于key的元素后移
        while (j >= p && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

// 分区函数，根据给定的基准值分区
int partition(int a[], int p, int r, int pivot) {
    // 找到基准元素并移到数组末尾
    int pivotIndex;
    for (pivotIndex = p; pivotIndex <= r; pivotIndex++) {
        if (a[pivotIndex] == pivot) {
            break;
        }
    }
    swap(&a[pivotIndex], &a[r]);

    pivot = a[r];  // 基准值
    int i = p - 1; // 小于基准区域的边界

    // 遍历数组进行分区
    for (int j = p; j <= r - 1; j++) {
        if (a[j] <= pivot) {
            i++;
            swap(&a[i], &a[j]);
        }
    }

    // 将基准放到正确位置
    swap(&a[i + 1], &a[r]);
    return i + 1;
}

// 中位数的中位数选择算法（迭代实现）
// 查找数组a[p..r]中第k小的元素
int select(int a[], int p, int r, int k) {
    while (1) {
        // 小规模数组直接排序后返回结果
        if (r - p < 75) {
            insertionSort(a, p, r);
            return a[p + k - 1];
        }

        // 将数组分成每组5个元素，找到每组的中位数并移到数组前面
        for (int i = 0; i <= (r - p - 4) / 5; i++) {
            // 对每组5个元素排序
            insertionSort(a, p + 5 * i, p + 5 * i + 4);
            // 将每组的中位数交换到数组前面
            swap(&a[p + i], &a[p + 5 * i + 2]);
        }

        // 计算中位数的中位数所在的位置，这里用循环代替递归
        int medianOfMedians_p = p;
        int medianOfMedians_r = p + (r - p - 4) / 5;
        int medianOfMedians_k = (r - p - 4) / 10 + 1;
        int medianOfMedians;
        while (1) {
            if (medianOfMedians_p == medianOfMedians_r) {
                medianOfMedians = a[medianOfMedians_p];
                break;
            }
            int pivotPos_med = randomizedPartition(a, medianOfMedians_p, medianOfMedians_r);
            int leftCount_med = pivotPos_med - medianOfMedians_p + 1;
            if (medianOfMedians_k <= leftCount_med) {
                medianOfMedians_r = pivotPos_med;
            }
            else {
                medianOfMedians_p = pivotPos_med + 1;
                medianOfMedians_k -= leftCount_med;
            }
        }

        // 以中位数的中位数为基准进行分区
        int pivotPos = partition(a, p, r, medianOfMedians);
        int leftCount = pivotPos - p + 1;  // 左分区元素个数

        // 判断第k小元素位置
        if (k <= leftCount) {
            r = pivotPos;
        }
        else {
            p = pivotPos + 1;
            k -= leftCount;
        }
    }
}

// 生成指定数量的随机数据并保存到文件
void generateRandomData(const char* filename, int count) {
    FILE* file = fopen(filename, "w");
    if (!file) {
        printf("无法打开文件 %s 进行写入！\n", filename);
        return;
    }

    // 设置随机数种子
    srand((unsigned int)time(NULL));

    // 生成并写入随机数
    for (int i = 0; i < count; i++) {
        // 生成0到1000000之间的随机数
        fprintf(file, "%d\n", rand() % 1000001);
    }

    fclose(file);
    printf("已生成 %d 个随机数据并保存到 %s\n", count, filename);
}

// 从文件读取数据
int* readDataFromFile(const char* filename, int* count) {
    FILE* file = fopen(filename, "r");
    if (!file) {
        printf("无法打开文件 %s 进行读取！\n", filename);
        *count = 0;
        return NULL;
    }

    // 先统计数据数量
    *count = 0;
    int temp;
    while (fscanf(file, "%d", &temp) == 1) {
        (*count)++;
    }

    // 分配内存
    int* data = (int*)malloc(*count * sizeof(int));
    if (!data) {
        printf("内存分配失败！\n");
        fclose(file);
        *count = 0;
        return NULL;
    }

    // 回到文件开头，读取数据
    rewind(file);
    for (int i = 0; i < *count; i++) {
        fscanf(file, "%d", &data[i]);
    }

    fclose(file);
    printf("已从 %s 读取 %d 个数据\n", filename, *count);
    return data;
}

// 比较函数，用于qsort排序验证结果
int compareInts(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

void testAlgorithms(int* originalData, int dataCount, int k) {
    int* data1 = (int*)malloc(dataCount * sizeof(int));
    memcpy(data1, originalData, dataCount * sizeof(int));

    clock_t startTime1 = clock();
    int result1 = randomizedSelect(data1, 0, dataCount - 1, k);
    clock_t endTime1 = clock();
    double time1 = (double)(endTime1 - startTime1) * 1000 / CLOCKS_PER_SEC;

    int* data3 = (int*)malloc(dataCount * sizeof(int));
    memcpy(data3, originalData, dataCount * sizeof(int));
    qsort(data3, dataCount, sizeof(int), compareInts);
    int correctResult = data3[k - 1];

    printf("\n--- 第 %d 小元素查找结果 ---\n", k);
    printf("正确结果: %d\n", correctResult);
    printf("随机选择算法: 结果=%d, 耗时=%.3f毫秒\n", result1, time1);

    if (result1 == correctResult) {
        printf("随机选择算法结果正确！\n");
    }
    else {
        printf("随机选择算法结果验证失败！\n");
    }

    free(data1);
    free(data3);
}

int main() {
    const char* filename = "test.txt";
    const int dataCount = 60000;  // 生成6万个数据
    const int k = 30000;          // 查找第3万小的元素（中位数附近）

    // 生成随机数据
    generateRandomData(filename, dataCount);

    // 从文件读取数据
    int count;
    int* data = readDataFromFile(filename, &count);
    if (!data || count == 0) {
        printf("数据读取失败，程序退出。\n");
        return 1;
    }

    // 测试算法
    testAlgorithms(data, count, k);
    // 释放内存
    free(data);
    return 0;
}